class Node(): #定义节点
    def __init__(self):
        self.next={}
        self.fail=None
        self.isWord=False

class Ahocorasick():
    def __init__(self):
        self.__root=Node()
    def addWord(self,word):
        temp=self.__root
        for i in range(0,len(word)):
            if word[i] not in temp.next:
                temp.next[word[i]]=Node()
            temp=temp.next[word[i]]
        temp.isWord=True

    def make(self):
        tmpQueue=[]
        tmpQueue.append(self.__root)
        while (len(tmpQueue))>0:
            temp=tmpQueue.pop()
            for k,v in temp.next.items():
                if temp==self.__root:
                    temp.next[k].fail=self.__root
                else:
                    p=temp.fail
                    while p is not None:
                        if k in p.next:
                            temp.next[k].fail=p.next[k]
                            break
                        p=p.fail
                    if p is None:
                        temp.next[k].fail=self.__root
                tmpQueue.append(temp.next[k])
    def search(self,content):
        p=self.__root
        result=[]
        startWordIndex=0
        currentPosition=0
        while currentPosition<len(content):
            word=content[currentPosition]
            while word in p.next==False and p!=self.__root:
                p=p.fail
            if word in p.next:
                if p==self.__root:
                    startWordIndex = currentPosition
                p=p.next[word]
            else:
                p=self.__root
            if p.isWord:
                result.append((startWordIndex,currentPosition))
            currentPosition+=1
        return result
if __name__=="__main__":
    ah=Ahocorasick()
    ah.addWord('你好')
    ah.make()
    result=ah.search('你好 我很开心')
    print(result)
